package com.LeeCode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 巫师的总力量和
 */

public class Code2281 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1, 1};
        System.out.println(new Code2281().totalStrength(nums));
    }

    public int totalStrength(int[] strength) {
        final int MOD = 1000000007;
        int n = strength.length;

        // Step 1: 前缀和 prefix[i] = sum(strength[0..i-1])
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
        }

        // Step 2: 前缀和的前缀和 pp[i] = prefix[0] + ... + prefix[i]
        long[] pp = new long[n + 2];
        for (int i = 0; i <= n; i++) {
            pp[i + 1] = (pp[i] + prefix[i]) % MOD;
        }

        // Step 3: 单调栈求 left[i] 和 right[i]
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);

        Deque<Integer> stack = new LinkedList<>();

        // 从左往右：找左边第一个 < strength[i]
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && strength[stack.peek()] >= strength[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }

        stack.clear();

        // 从右往左：找右边第一个 < strength[i]（用 >= 弹出）
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && strength[stack.peek()] > strength[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                right[i] = stack.peek();
            }
            stack.push(i);
        }

        // Step 4: 枚举每个 i 作为最小值
        long total = 0;
        for (int i = 0; i < n; i++) {
            int L1 = left[i] + 1;  // 左边界起点
            int R1 = i;
            int L2 = i;
            int R2 = right[i] - 1;

            int lenLeft = R1 - L1 + 1;  // 左边可选起点数
            int lenRight = R2 - L2 + 1; // 右边可选终点数

            // 计算 sum_{r=i}^{R2} prefix[r+1]
            long sumPrefixR = (pp[R2 + 2] - pp[i + 1] + MOD) % MOD;
            // 计算 sum_{l=L1}^{i} prefix[l]
            long sumPrefixL = (pp[i + 1] - pp[L1] + MOD) % MOD;

            // 所有子数组的 sum(l,r) 之和 = lenLeft * sumPrefixR - lenRight * sumPrefixL
            long sumOfSums = (lenLeft * sumPrefixR % MOD - lenRight * sumPrefixL % MOD + MOD) % MOD;

            // 当前 i 的贡献 = strength[i] * sumOfSums
            long contrib = strength[i] * sumOfSums % MOD;
            total = (total + contrib) % MOD;
        }

        return (int) total;
    }
}
